package com.zxy.leetcode._00000_00099._00040_00049;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/combination-sum/
 *
 * 组合总和
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，
 * 找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 *
 * 标签：回溯算法
 *
 * 我去除是用Set集合，
 * 有人通过“i > begin && candidates[i] == candidates[i - 1”解决
 * https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
 *
 */
public class Test00040 {

    public static void main(String[] args) {
        Test00040 test = new Test00040();

        int[] nums1 = {10,1,2,7,6,1,5};
        System.out.println(test.combinationSum2(nums1, 8));

        int[] nums2 = {2,5,2,1,2};
        System.out.println(test.combinationSum2(nums2, 5));
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int sum = 0;
        for (int num : candidates) {
            sum += num;
        }
        if (sum < target) {
            return Collections.emptyList();
        }

        Arrays.sort(candidates);
        if (candidates[0] > target) {
            return Collections.emptyList();
        }

        Set<List<Integer>> result = new HashSet<>();
        backtrack(result, new LinkedList<>(), candidates, target);

        return new ArrayList<>(result);
    }

    private void backtrack(Set<List<Integer>> result, LinkedList<Integer> selectIndexs, int[] allNums, int target) {
        if (sum(allNums, selectIndexs) == target) {
            List<Integer> list = new ArrayList<>(selectIndexs.size());
            for (int index : selectIndexs) {
                list.add(allNums[index]);
            }
            result.add(list);
            return;
        }

        for (int i=0; i<allNums.length; i++) {
            // 重复判断
            if (selectIndexs.size() > 0 && selectIndexs.getLast() >= i) {
                continue;
            }

            // 基于升序数组考虑
            if (sum(allNums, selectIndexs) + allNums[i] > target) {
                return;
            }

            selectIndexs.add(i);
            backtrack(result, selectIndexs, allNums, target);
            selectIndexs.removeLast();
        }
    }

    private int sum(int[] allNums, List<Integer> selectIndexs) {
        if (selectIndexs.size() == 0) {
            return 0;
        }
        int sum = 0;
        for (int index : selectIndexs) {
            sum += allNums[index];
        }
        return sum;
    }

}
